package exp8;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class DAGParent {
    public static void main(String[] args) {
        int n = 8;
        int[][] edgeList = {{0, 3}, {0, 4}, {1, 3}, {2, 4}, {2, 7}, {3, 5}, {3, 6}, {3, 7}, {4, 6}};
        DAGParentSolution solution = new DAGParentSolution();
        List<List<Integer>> result = solution.getAncestors(n, edgeList);
        System.out.println(result);

    }
}

class DAGParentSolution {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        List<List<Integer>> res = new ArrayList<>();
        // graph用于记录from 和 to
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<Integer>());
        }
        // 将i的祖先放在数组i中
        for (int i = 0; i < edges.length; i++) {
            graph.get(edges[i][1]).add(edges[i][0]);
        }
        for (int i = 0; i < n; i++) {
            int[] visited = new int[n];
            List<Integer> temp = new ArrayList<>();
            DFS(graph, temp, visited, i);
            temp.sort(Comparator.naturalOrder());//自然排序。例如数字、字母等。
            res.add(temp);
        }
        return res;
    }

    public void DFS(List<List<Integer>> graph, List<Integer> temp, int[] visited, int x) {
        visited[x] = 1;
        for (int i = 0; i < graph.get(x).size(); i++) {
            if (visited[graph.get(x).get(i)] == 0) {
                visited[graph.get(x).get(i)] = 1;
                temp.add(graph.get(x).get(i));
                DFS(graph, temp, visited, graph.get(x).get(i));
            }
        }
    }
}



